package com.sh.stack;

/**
 * @ClassName Calculate
 * @Description TODO
 * @Author yaoqiang
 * @Date 2020/11/5 16:19
 * @Version 1.0
 */
public class Calculate {
    public static void main(String[] args) {
        //中缀表达式-一位数的基本运算的基本思想
        //定义栈，入栈，出栈，计算方法，isFull,isEmpty,判断是不是运算符，判断符号优先级
        /***
         * 栈的三种表达式：
         * 前缀表达式：波兰表达式，前缀表达式的运算符位于操作数之前，eg: (3+4)*5-6 前缀表达式是 -*+3456
         *从右向左扫描，
         * 中缀：对计算机不好理解， 需要判断优先级，所以一般把中缀表达式转成后缀表达式，逆波兰表达式
         * 后缀（逆波兰表达式）操作符位于操作数之后eg: (3+4)*5-6 前缀表达式是 34+5*6-
         * 从左向右扫描，遇到数字压入栈，遇到运算符，弹出栈顶的两个元素，用操作数做运算，将结果压入栈，重复知道最右端
         */
        String expression="7012+2*6-2";
        //定义两个栈，一个是树栈，一个是符号栈
        ArrayStack2 numStack=new ArrayStack2(10);
        ArrayStack2 operStack=new ArrayStack2(10);
        //定义变量
        int index=0;//用于扫描
        int num1=0;
        int num2=0;
        int oper=0;
        int result=0;
        char ch=' ';//将每次扫描的char保存到ch
        String keepNum="";//用来拼接数
        while (true){
            //先每次扫描每个字符
            ch=expression.substring(index,index+1).charAt(0);
            //判断ch是什么然后做相应的处理
            if (operStack.isOper( ch)){
                //判断当前符号栈是否为空
                if (!operStack.isEmpty()){
                    //不为空，如果有操作符，进行比较，当前操作符的优先级小于或者等于栈中的操作符，需要从数栈中pop出两个数，
                    //从符号栈pop出一个符号进行运算，将得到的结果入数栈，将当前操作符入符号栈。
                    if (operStack.priority(ch)<=operStack.priority(operStack.peek())){
                        //从数栈pop出两个数进行运算
                        num1=numStack.pop();
                        num2=numStack.pop();
                        oper=operStack.pop();
                        result=numStack.cal(num1,num2,oper);
                        //把结果入数栈
                        numStack.push(result);
                        //然后将当前操作符入数栈
                        operStack.push(ch);

                    }else{
                        //如果当前的操作符的优先级大于栈中的操作符，直接入符号栈
                        operStack.push(ch);
                    }
                }else {

                    //空入栈
                    operStack.push(ch); //1+3
                }

            }else{
                //当处理多位数，不能发现是数就立即入数栈，可能是多位数
                //在处理数时，想表达式后面再看一位，如果是数继续扫描， 如果是符号才入栈，需要定义一个字符串变量用于拼接
                 keepNum+=ch;
                 //如果当前是最后一位
                if(index==expression.length()-1){
                    numStack.push(Integer.parseInt(keepNum));
                }else {
                    //判断下一个数是不是数字，直到遇到运算符，才停止
                    if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
                        //如果后一位是操作符则入栈
                        numStack.push(Integer.parseInt(keepNum));//将字符"1"转成数字1
                        //必须将清空keepNum
                        keepNum="";
                    }
                }



                //如果是数，直接入数栈
             //   numStack.push(ch-48);//将字符"1"转成数字1

            }
            index++;
            //让index+1,判断是否扫描到表达式最后
            if(index>=expression.length()){
                break;
            }
        }
        //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运算
        while (true){
            //如果符号栈为空，则计算结束，结算到最后的结果，数栈只有一个数字就是结果
            if (operStack.isEmpty()){
                break;
            }else {
                num1=numStack.pop();
                num2=numStack.pop();
                oper=operStack.pop();
                result=numStack.cal(num1,num2,oper);
                numStack.push(result);
            }
        }
        //将数栈最后的数pop出来
        System.out.println(expression+"="+numStack.pop());
    }
}
/**
 * 使用栈完成表达式的计算思路
 * 1、通过一个index的值，当做索引来遍历我们的表达式
 * 2、如果我们扫描到的是数字，入数栈，如果是符号分情况
 *如果符号栈为空，直接入栈
 * 如果符号栈有操作符，就进行比较，如果当前操作符的优先级小于等于栈中的操作符，就需要从数栈中pop出两个数，进行运算得到结果，入数栈，然后将当前操作符入符号栈，如果当前操作符优先级大于栈中的操作符，直接入符号栈
 * 当表达式运算完，就顺序的pop出
 * 验证3+2*6-2
 * 1、3入栈，+入栈
 * 2、2入栈，*比较，比较+，优先级高，所以*入栈
 * 3、6入数字栈，-号优先级小于栈中优先级，从数字栈pop2个数和一个符号进行运算6*2得到12，将结果12入数栈，-入符号栈
 *4、2入栈
 * 运算的过程中，一定是后面弹出的数-前面的数
 * 从顶往底处理
 *
 *
 */


class ArrayStack2{
    private  int maxSize;//栈的大小
    private int[] stack;//数组模拟栈，数据就放在该数组
    private int top=-1; //top表示栈顶，初始化为-1
    //构造器
    public ArrayStack2(int maxSize){
        this.maxSize=maxSize;
        stack=new int[maxSize];
    }
    //栈满
    public boolean isFull(){
        return top==maxSize-1;
    }

    //栈空
    public boolean isEmpty(){
        return top ==-1;
    }
    //入栈
    public void push(int value){
        if (isFull()){
            System.out.println("栈满");return;
        }
        top++;
        stack[top]=value;
    }
    //出栈
    public  int  pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空");
        }
        int value=stack[top];
        top--;
        return value;
    }
    public void list(){
        if (isEmpty()){return;}
        for (int i=top;i>=0;i--){
            System.out.println(stack[i]);
        }
    }
    //返回运算符的优先级，使用数字表示，数字越大优先级越高

    public  int priority(int oper){
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;//假定表达式只有+-*/
        }
    }
    //判断是不是一个运算符
    public boolean isOper(char val){
        return val =='+'||val =='-' ||val=='*'||val=='/';
    }

    //计算方法，
    public int cal(int num1,int num2,int oper){
        int res=0;
        switch (oper){
            case '+':res=num1+num2; break;
            case '-':res=num2-num1; break;
            case '*':res=num1*num2; break;
            case '/':res=num2/num1; break;
            default:break;
        }
        return res;
    }

    //peek方法,返回当前栈顶的值，但不是真正出栈
    public int peek(){
        return stack[top];
    }

}
